{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Course Schedule"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #depth-first-search #breadth-first-search #graph #topological-sort"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #深度优先搜索 #广度优先搜索 #图 #拓扑排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: canFinish"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #课程表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>你这个学期必须选修 <code>numCourses</code> 门课程，记为&nbsp;<code>0</code>&nbsp;到&nbsp;<code>numCourses - 1</code> 。</p>\n",
    "\n",
    "<p>在选修某些课程之前需要一些先修课程。 先修课程按数组&nbsp;<code>prerequisites</code> 给出，其中&nbsp;<code>prerequisites[i] = [a<sub>i</sub>, b<sub>i</sub>]</code> ，表示如果要学习课程&nbsp;<code>a<sub>i</sub></code> 则 <strong>必须</strong> 先学习课程&nbsp; <code>b<sub>i</sub></code><sub> </sub>。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>例如，先修课程对&nbsp;<code>[0, 1]</code> 表示：想要学习课程 <code>0</code> ，你需要先完成课程 <code>1</code> 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>请你判断是否可能完成所有课程的学习？如果可以，返回 <code>true</code> ；否则，返回 <code>false</code> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>numCourses = 2, prerequisites = [[1,0]]\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：</strong>总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>numCourses = 2, prerequisites = [[1,0],[0,1]]\n",
    "<strong>输出：</strong>false\n",
    "<strong>解释：</strong>总共有 2 门课程。学习课程 1 之前，你需要先完成​课程 0 ；并且学习课程 0 之前，你还应先完成课程 1 。这是不可能的。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= numCourses &lt;= 2000</code></li>\n",
    "\t<li><code>0 &lt;= prerequisites.length &lt;= 5000</code></li>\n",
    "\t<li><code>prerequisites[i].length == 2</code></li>\n",
    "\t<li><code>0 &lt;= a<sub>i</sub>, b<sub>i</sub> &lt; numCourses</code></li>\n",
    "\t<li><code>prerequisites[i]</code> 中的所有课程对 <strong>互不相同</strong></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [course-schedule](https://leetcode.cn/problems/course-schedule/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [course-schedule](https://leetcode.cn/problems/course-schedule/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['2\\n[[1,0]]', '2\\n[[1,0],[0,1]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasLoop(self, u: int, follow: Dict[int, Set[int]], visited: List[int], path: Set[int]) -> bool:\n",
    "        if u in path:\n",
    "            return True\n",
    "        if visited[u]:\n",
    "            return False\n",
    "\n",
    "        visited[u] = True\n",
    "        path.add(u)\n",
    "        has_loop_down: bool = any(self.hasLoop(v, follow, visited, path) for v in follow[u])\n",
    "        path.remove(u)\n",
    "\n",
    "        return has_loop_down\n",
    "\n",
    "\n",
    "    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:\n",
    "        has_prereq: List[bool] = [False] * numCourses\n",
    "        follow: Dict[int, Set[int]] = {i: set() for i in range(numCourses)}\n",
    "        for v, u in prerequisites:\n",
    "            if v == u:\n",
    "                return False\n",
    "            follow[u].add(v)\n",
    "            has_prereq[v] = True\n",
    "\n",
    "        start: List[int] = [i for i, tf in enumerate(has_prereq) if not tf]\n",
    "        if len(start) == 0:\n",
    "            return False\n",
    "\n",
    "        visited: List[bool] = [False] * numCourses\n",
    "        return (\n",
    "            all(\n",
    "                not self.hasLoop(root, follow, visited, set())\n",
    "                for root in start\n",
    "            )\n",
    "            and all(visited)\n",
    "        )\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canFinish(self, numCourses, prerequisites):\n",
    "        \"\"\"\n",
    "        :type numCourses: int\n",
    "        :type prerequisites: List[List[int]]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        if numCourses < 2 or len(prerequisites) < 2:\n",
    "            return True\n",
    "        while True:\n",
    "            count = 0\n",
    "            mark = [True]*numCourses #true表示入度为0 删除与之的依赖关系\n",
    "            for pre in prerequisites:\n",
    "                mark[pre[0]] = False\n",
    "            for pre in prerequisites:\n",
    "                if mark[pre[1]]:\n",
    "                    count += 1\n",
    "                    prerequisites.remove(pre)\n",
    "            if prerequisites == []:\n",
    "                return True\n",
    "            elif count == 0:\n",
    "                return False\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canFinish(self, numCourses, prerequisites):\n",
    "        \"\"\"\n",
    "        :type numCourses: int\n",
    "        :type prerequisites: List[List[int]]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        degree,count,queue=[0 for i in range(numCourses)],0,[]\n",
    "        graph=[[] for i in range(numCourses)]\n",
    "        \n",
    "        \n",
    "        for temp in prerequisites:\n",
    "            degree[temp[1]]+=1\n",
    "            graph[temp[0]].append(temp[1])\n",
    "            \n",
    "        for i in range(len(degree)):\n",
    "            if degree[i]==0:\n",
    "                queue.append(i)\n",
    "                count+=1\n",
    "                \n",
    "        while queue:\n",
    "            course=queue.pop(0)\n",
    "            for i in range(len(graph[course])):\n",
    "                degree[graph[course][i]]-=1\n",
    "                if  degree[graph[course][i]]==0:\n",
    "                    queue.append(graph[course][i])\n",
    "                    count+=1\n",
    "                    \n",
    "        return count==numCourses"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    def canFinish(self, numCourses: 'int', prerequisites: 'List[List[int]]') -> 'bool':\n",
    "        \n",
    "        from collections import defaultdict\n",
    "        paths = defaultdict(set)\n",
    "        s = []\n",
    "        inDegree = [ 0 for _ in range(numCourses)]\n",
    "            \n",
    "        # 构建入度\n",
    "        for pre in prerequisites:\n",
    "            inDegree[pre[0]] += 1\n",
    "            paths[pre[1]].add(pre[0])\n",
    "            \n",
    "        # 将入度为0 的节点存入到s中\n",
    "        for i in range(len(inDegree)):\n",
    "            if inDegree[i] == 0:\n",
    "                s.append(i)\n",
    "                numCourses -= 1\n",
    "        while s:\n",
    "            node = s.pop()\n",
    "            for k in paths[node]:\n",
    "                inDegree[k] -= 1\n",
    "                if inDegree[k] == 0:\n",
    "                    s.append(k)\n",
    "                    numCourses -= 1\n",
    "        \n",
    "        return (numCourses == 0)\n",
    "\n",
    "\n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canFinish(self, numCourses, prerequisites):\n",
    "        \"\"\"\n",
    "        :type numCourses: int\n",
    "        :type prerequisites: List[List[int]]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        d = {}\n",
    "        for i in range(numCourses):\n",
    "            d[i] = [0, []]\n",
    "        for a, b in prerequisites:\n",
    "            d[a][0] += 1\n",
    "            d[b][1].append(a)\n",
    "        front = []\n",
    "        for k in d.keys():\n",
    "            if d[k][0] == 0:\n",
    "                front.append(k)\n",
    "        while front:\n",
    "            next_front = []\n",
    "            for k in front:\n",
    "                for b in d[k][1]:\n",
    "                    d[b][0] -= 1\n",
    "                    if d[b][0] == 0:\n",
    "                        next_front.append(b)\n",
    "                del d[k]\n",
    "            front = next_front\n",
    "        return len(d) == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution(object):\n",
    "    def canFinish(self, N, prerequisites):\n",
    "        \"\"\"\n",
    "        :type N,: int\n",
    "        :type prerequisites: List[List[int]]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        graph = collections.defaultdict(list)\n",
    "        for u, v in prerequisites:\n",
    "            graph[u].append(v)\n",
    "        # 0 = Unknown, 1 = visiting, 2 = visited\n",
    "        visited = [0] * N\n",
    "        for i in range(N):\n",
    "            if not self.dfs(graph, visited, i):\n",
    "                return False\n",
    "        return True\n",
    "        \n",
    "    # Can we add node i to visited successfully?\n",
    "    def dfs(self, graph, visited, i):\n",
    "        if visited[i] == 1: return False\n",
    "        if visited[i] == 2: return True\n",
    "        visited[i] = 1\n",
    "        for j in graph[i]:\n",
    "            if not self.dfs(graph, visited, j):\n",
    "                return False\n",
    "        visited[i] = 2\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def depth_first_search_cycle(self, v):\n",
    "        self.marked[v] = True\n",
    "        self.onStack[v] = True\n",
    "        if self.hasCycle == True:\n",
    "            return\n",
    "        \n",
    "        for w in self.vertices[v]:\n",
    "            if self.marked[w] == False:\n",
    "                self.depth_first_search_cycle(w)\n",
    "            elif self.onStack[w] == True:\n",
    "                self.hasCycle = True\n",
    "                return\n",
    "        self.onStack[v] = False\n",
    "    \n",
    "    def canFinish(self, numCourses, prerequisites):\n",
    "        if numCourses == 0:\n",
    "            return False\n",
    "        elif numCourses == 1:\n",
    "            return True\n",
    "        \n",
    "        self.marked = [False] * numCourses\n",
    "        self.onStack = [False] * numCourses\n",
    "        self.hasCycle = False\n",
    "        self.vertices = {}\n",
    "        \n",
    "        for w in prerequisites:\n",
    "            w_0 = w[0]\n",
    "            w_1 = w[1]\n",
    "            if w_0 not in self.vertices.keys():\n",
    "                self.vertices[w_0] = []\n",
    "            if w_1 not in self.vertices.keys():\n",
    "                self.vertices[w_1] = []\n",
    "            tmp = self.vertices[w_0]\n",
    "            tmp.append(w_1)\n",
    "            self.vertices[w_0] = tmp\n",
    "            \n",
    "        for w in self.vertices.keys():\n",
    "            if self.marked[w] == False:\n",
    "                self.depth_first_search_cycle(w)\n",
    "        return False if self.hasCycle == True else True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canFinish(self, numCourses, prerequisites):\n",
    "        \"\"\"\n",
    "        :type numCourses: int\n",
    "        :type prerequisites: List[List[int]]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        forward = {i: set() for i in range(numCourses)}\n",
    "        backward = collections.defaultdict(set)\n",
    "        for i, j in prerequisites:\n",
    "            forward[i].add(j)\n",
    "            backward[j].add(i)\n",
    "        queue = collections.deque([node for node in forward if len(forward[node]) == 0])\n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "            for neigh in backward[node]:\n",
    "                forward[neigh].remove(node)\n",
    "                if len(forward[neigh]) == 0:\n",
    "                    queue.append(neigh)\n",
    "            forward.pop(node)\n",
    "        return not forward \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "\n",
    "    # 这里使用前驱邻接表\n",
    "\n",
    "    def canFinish(self, numCourses, prerequisites):\n",
    "        \"\"\"\n",
    "        :type numCourses: int 课程门数\n",
    "        :type prerequisites: List[List[int]] 课程与课程之间的关系\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        # 课程的长度\n",
    "        clen = len(prerequisites)\n",
    "        if clen == 0:\n",
    "            # 没有课程，当然可以完成课程的学习\n",
    "            return True\n",
    "        # 深度优先遍历，判断结点是否访问过\n",
    "        # 这里要设置 3 个状态\n",
    "        # 0 就对应 False ，表示结点没有访问过\n",
    "        # 1 就对应 True ，表示结点已经访问过，在深度优先遍历结束以后才置为 1\n",
    "        # 2 表示当前正在遍历的结点，如果在深度优先遍历的过程中，\n",
    "        # 有遇到状态为 2 的结点，就表示这个图中存在环\n",
    "        visited = [0 for _ in range(numCourses)]\n",
    "\n",
    "        # 逆邻接表，存的是每个结点的前驱\n",
    "        # 想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们: [0,1]\n",
    "        # 1 在前，0 在后\n",
    "        adj = [set() for _ in range(numCourses)]\n",
    "        for second, first in prerequisites:\n",
    "            adj[second].add(first)\n",
    "\n",
    "        for i in range(numCourses):\n",
    "            # 在遍历的过程中，如果发现有环，就退出\n",
    "            if self.__dfs(i, adj, visited):\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "    def __dfs(self, vertex, adj, visited):\n",
    "        \"\"\"\n",
    "        注意：这个递归方法的返回值是返回是否有环\n",
    "        :param vertex:\n",
    "        :param adj:\n",
    "        :param visited:\n",
    "        :param res:\n",
    "        :return: 是否有环\n",
    "        \"\"\"\n",
    "        # 2 表示这个结点正在访问\n",
    "        if visited[vertex] == 2:\n",
    "            # 表示遇到环\n",
    "            return True\n",
    "        if visited[vertex] == 1:\n",
    "            return False\n",
    "\n",
    "        visited[vertex] = 2\n",
    "        for successor in adj[vertex]:\n",
    "            # 如果有环，就返回 True 表示有环\n",
    "            if self.__dfs(successor, adj, visited):\n",
    "                return True\n",
    "        # 1 表示访问结束\n",
    "        visited[vertex] = 1\n",
    "        # 注意理解这一步：把所有的后继全部访问了一遍，先输出的是没有后继的结点\n",
    "        # 能走到最后，表示无环\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canFinish(self, numCourses, prerequisites):\n",
    "        \"\"\"\n",
    "        :type numCourses: int\n",
    "        :type prerequisites: List[List[int]]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        graph = [[] for _ in range(numCourses)]\n",
    "        visit = [0 for _ in range(numCourses)]\n",
    "        for x, y in prerequisites:\n",
    "            graph[x].append(y)\n",
    "        \n",
    "        def dfs(i):\n",
    "            if visit[i] == -1:\n",
    "                return False\n",
    "            if visit[i] == 1:\n",
    "                return True\n",
    "            visit[i] = -1\n",
    "            for j in graph[i]:\n",
    "                if not dfs(j):\n",
    "                    return False\n",
    "            visit[i] = 1\n",
    "            return True                \n",
    "    \n",
    "        for i in range(numCourses):\n",
    "            #print(i)\n",
    "           # print(visit)\n",
    "            if not dfs(i):\n",
    "                return False\n",
    "        return True\n",
    "            \n",
    "            \n",
    "            \n",
    "        \n",
    "        \n",
    "                    \n",
    "            \n",
    "            \n",
    "            \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canFinish(self, numCourses: 'int', prerequisites: 'List[List[int]]') -> 'bool':\n",
    "        global flag\n",
    "        global color\n",
    "        if numCourses == 1:\n",
    "            return True\n",
    "\n",
    "        vec={}\n",
    "        color=[-1] * numCourses\n",
    "        flag = True\n",
    "\n",
    "        for i in range(numCourses):\n",
    "            vec[i]=[]\n",
    "\n",
    "        for i in prerequisites:\n",
    "            vec[i[0]].append(i[1])\n",
    "\n",
    "        def dfs(x:'int'):\n",
    "            global flag\n",
    "            global color\n",
    "            if not flag:\n",
    "                return None\n",
    "            if color[x] == 1:\n",
    "                return None\n",
    "            color[x]=0\n",
    "            for i in vec[x]:\n",
    "                if color[i] == -1:\n",
    "                    dfs(i)\n",
    "                elif color[i] == 0:\n",
    "                    flag = False\n",
    "                    return None\n",
    "            else:\n",
    "                color[x] = 1\n",
    "\n",
    "        for j in range(numCourses):\n",
    "            dfs(j)\n",
    "            if not flag:\n",
    "                break\n",
    "        \n",
    "        return flag"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canFinish(self, numCourses: 'int', prerequisites: 'List[List[int]]') -> 'bool':\n",
    "        # if len(prerequisites) < 2 or numCourses < 2:\n",
    "        #     return True\n",
    "        # inDegree = [0] * numCourses\n",
    "        # for pre in prerequisites:\n",
    "        #     inDegree[pre[0]] += 1\n",
    "        graph = {}\n",
    "        memo = set()\n",
    "        for x, y in prerequisites:\n",
    "            if y not in graph:\n",
    "                graph[y] = set()\n",
    "            graph[y].add(x)\n",
    "        def dfs(start, visited):\n",
    "            if start in visited:\n",
    "                return False\n",
    "            if start in memo:\n",
    "                return True\n",
    "            visited.add(start)\n",
    "            if start in graph:\n",
    "                for nextnode in graph[start]:\n",
    "                    if not dfs(nextnode, visited):\n",
    "                        return False\n",
    "            visited.discard(start)\n",
    "            memo.add(start)\n",
    "            return True\n",
    "        for start in graph:\n",
    "            if not dfs(start, set()):\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef __init__(self):\n",
    "\t\tself.visiting = None#[False for i in range(n)]\n",
    "\t\tself.visited = None#[False for i in range(n)]\n",
    "\t\n",
    "\tdef canFinish(self, numCourses, prerequisites):\n",
    "\t\t\"\"\"\n",
    "\t\t:type numCourses: int\n",
    "\t\t:type prerequisites: List[List[int]]\n",
    "\t\t:rtype: bool\n",
    "\t\t\"\"\"\n",
    "\t\tself.visiting = [False for i in range(numCourses)]\n",
    "\t\tself.visited = [False for i in range(numCourses)]\n",
    "\t\tg = [[] for i in range(numCourses)]\n",
    "\t\tfor i in range(len(prerequisites)):\n",
    "\t\t\tg[prerequisites[i][0]].append(prerequisites[i][1])\n",
    "\n",
    "\t\tfor i in range(numCourses):\n",
    "\t\t\tif not self.visited[i] and not self.DFS(g, i):\n",
    "\t\t\t\treturn False\n",
    "\t\treturn True\n",
    "\t\t\n",
    "\t\t\n",
    "\tdef DFS(self, g, start):\n",
    "\t\tself.visited[start] = True\n",
    "\t\tif self.visiting[start]:\n",
    "\t\t\treturn False\n",
    "\t\tself.visiting[start] = True\n",
    "\t\tfor node in g[start]:\n",
    "\t\t\tif not self.DFS(g, node):\n",
    "\t\t\t\treturn False\n",
    "\t\tself.visiting[start] = False\n",
    "\t\treturn True\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def canFinish(self, numCourses, prerequisites):\n",
    "#         \"\"\"\n",
    "#         Kahn算法 56ms 99.39%\n",
    "#         :type numCourses: int\n",
    "#         :type prerequisites: List[List[int]]\n",
    "#         :rtype: bool\n",
    "#         \"\"\"\n",
    "#         in_degree = {i: 0 for i in range(numCourses)}\n",
    "#         node_edges = {}\n",
    "#         for u, v in prerequisites:\n",
    "#             in_degree[u] += 1\n",
    "#             if v in node_edges:\n",
    "#                 node_edges[v].add(u)\n",
    "#             else:\n",
    "#                 node_edges[v] = {u}\n",
    "#         Q = set(v for v, d in in_degree.items() if d == 0)\n",
    "#         while Q:\n",
    "#             u = Q.pop()\n",
    "#             in_degree.pop(u)\n",
    "#             if u in node_edges:\n",
    "#                 for v in node_edges[u]:\n",
    "#                     in_degree[v] -= 1\n",
    "#                     if in_degree[v] == 0:\n",
    "#                         Q.add(v)\n",
    "#         return not bool(in_degree)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def canFinish(self, numCourses, prerequisites):\n",
    "        \"\"\"\n",
    "        dfs\n",
    "        \"\"\"\n",
    "        node_edges = {}\n",
    "        for u, v in prerequisites:\n",
    "            if v in node_edges:\n",
    "                node_edges[v].add(u)\n",
    "            else:\n",
    "                node_edges[v] = {u}\n",
    "        \n",
    "        per = set()\n",
    "        tem = set()\n",
    "        \n",
    "        def _dfs(u):\n",
    "            if u in per: return True\n",
    "            if u in tem: return False\n",
    "            tem.add(u)\n",
    "            if u in node_edges:\n",
    "                for v in node_edges[u]:\n",
    "                    if not _dfs(v):\n",
    "                        return False\n",
    "            per.add(u)\n",
    "            return True\n",
    "        \n",
    "        for i in range(numCourses):\n",
    "            if not _dfs(i):\n",
    "                return False\n",
    "        \n",
    "        return True\n",
    "            \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def canFinish(self, numCourses, prerequisites):\n",
    "        \"\"\"\n",
    "        :type numCourses: int\n",
    "        :type prerequisites: List[List[int]]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        pre = defaultdict(list)\n",
    "        for p, q in prerequisites:\n",
    "            pre[p].append(q)\n",
    "            \n",
    "        visited = set()\n",
    "        visiting = set()\n",
    "        \n",
    "        def visit(node):\n",
    "            if node in visiting:\n",
    "                return False\n",
    "            \n",
    "            visiting.add(node)\n",
    "            result = True\n",
    "            \n",
    "            for next_ in pre[node]:\n",
    "                \n",
    "                result = result and visit(next_)\n",
    "                \n",
    "            visiting.remove(node)\n",
    "            visited.add(node)\n",
    "            return result\n",
    "        \n",
    "        for node in range(numCourses):\n",
    "            if node not in visited:\n",
    "                if not visit(node):\n",
    "                    return False\n",
    "                \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def canFinish(self, numCourses, prerequisites):\n",
    "        if not numCourses or not prerequisites:\n",
    "            return True  # 没有课程不用修，没有先修条件肯定能修完课\n",
    "\n",
    "        in_degrees = [0 for _ in range(numCourses)]  # 入度数组，一开始全部为 0，数组下标即节点的索引号\n",
    "        adj = [set() for _ in range(numCourses)]  # 邻接表，存放某节点的后继结点的集合，使用 set 是为了去重\n",
    "\n",
    "        # 统计每个顶点的入度，并获得邻接表。\n",
    "        for second, first in prerequisites:\n",
    "            in_degrees[second] += 1\n",
    "            adj[first].add(second)\n",
    "\n",
    "        queue = [i for i in range(numCourses) if in_degrees[i] == 0]  # 首先把所有入度为 0 的结点都加入队列\n",
    "        numCourses -= len(queue)  # 入度为 0 的结点数\n",
    "        while queue:  # 遍历所有入度为零的节点\n",
    "            top = queue.pop(0)\n",
    "            for successor in adj[top]:  # 若为空 set 则不遍历\n",
    "                in_degrees[successor] -= 1  # 后继节点的入度减一\n",
    "                if in_degrees[successor] == 0:  # 入度为 0，添加到队列中,计数加一\n",
    "                    queue.append(successor)\n",
    "                    numCourses -= 1\n",
    "        return numCourses == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:\n",
    "        if not numCourses:\n",
    "            return True\n",
    "        indegree = [0 for _ in range(numCourses)]\n",
    "        injacency = [[] for _ in range(numCourses)]\n",
    "        for cur,pre in prerequisites:\n",
    "            indegree[cur] += 1\n",
    "            injacency[pre].append(cur)\n",
    "        \n",
    "        q =[]\n",
    "        for i in range(numCourses):\n",
    "            if not indegree[i]: \n",
    "                q.append(i)\n",
    "        \n",
    "        while q:\n",
    "            node = q.pop(0)\n",
    "            numCourses -= 1\n",
    "            for cur in injacency[node]:\n",
    "                indegree[cur] -= 1\n",
    "                if not indegree[cur]: q.append(cur)\n",
    "        \n",
    "        return not numCourses\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# from collections import deque\n",
    "\n",
    "class Solution:\n",
    "    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:\n",
    "        n=numCourses\n",
    "        dingdian_rudushu=[0 for i in range(n)]\n",
    "        houxiu_dingdian=[[] for i in range(n)]\n",
    "        queue=[]\n",
    "        for houxiu,pre in prerequisites:\n",
    "            dingdian_rudushu[houxiu]+=1\n",
    "            houxiu_dingdian[pre].append(houxiu) #某个顶点的后修顶点们\n",
    "        for i in range(n):\n",
    "            if dingdian_rudushu[i]==0:\n",
    "                queue.append(i)\n",
    "                numCourses-=1\n",
    "        while queue:\n",
    "            pre=queue.pop(0)\n",
    "            for houxiu in houxiu_dingdian[pre]:\n",
    "                dingdian_rudushu[houxiu]-=1\n",
    "                if dingdian_rudushu[houxiu]==0:\n",
    "                    queue.append(houxiu)\n",
    "                    numCourses-=1\n",
    "        return numCourses==0\n",
    "                \n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:\n",
    "        course_pre_count = {}\n",
    "        for prerequisite in prerequisites:\n",
    "            course = prerequisite[0]\n",
    "            course_pre_count[course] = course_pre_count.get(course, 0) + 1 \n",
    "        finished = deque([course for course in range(numCourses) if course not in course_pre_count])\n",
    "        # for course in course_pre_count:\n",
    "        #     if course_pre_count[course] == 0:\n",
    "        #         finished.append(course)\n",
    "        while finished:\n",
    "            finished_course = finished.popleft()\n",
    "            for prerequisite in prerequisites:\n",
    "                to_learn_course = prerequisite[0]\n",
    "                if course_pre_count[to_learn_course] <= 0:\n",
    "                    continue\n",
    "                elif finished_course in prerequisite:\n",
    "                    course_pre_count[to_learn_course] -= 1\n",
    "                    if course_pre_count[to_learn_course] == 0:\n",
    "                        finished.append(to_learn_course)\n",
    "        # print(course_pre_count)\n",
    "        for course in course_pre_count:\n",
    "            if course_pre_count[course] != 0:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:\n",
    "        indegree = [0]*numCourses\n",
    "        adjency_graph = [[] for _ in range(numCourses)]\n",
    "        \n",
    "        for pre,cur in prerequisites:\n",
    "            indegree[cur]+=1\n",
    "            adjency_graph[pre].append(cur)\n",
    "        queue = deque()\n",
    "        for i in range(numCourses):\n",
    "            if indegree[i] == 0:\n",
    "                queue.append(i)\n",
    "        while queue:\n",
    "            t = queue.popleft()\n",
    "            for i in adjency_graph[t]:\n",
    "                indegree[i]-=1\n",
    "                if indegree[i]==0:\n",
    "                    queue.append(i)\n",
    "            numCourses-=1\n",
    "        return numCourses==0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:\n",
    "        edges = collections.defaultdict(list)\n",
    "        indeg = [0] * numCourses\n",
    "\n",
    "        for info in prerequisites:\n",
    "            edges[info[1]].append(info[0])\n",
    "            indeg[info[0]] += 1\n",
    "        \n",
    "        q = collections.deque([u for u in range(numCourses) if indeg[u] == 0])\n",
    "        visited = 0\n",
    "\n",
    "        while q:\n",
    "            visited += 1\n",
    "            u = q.popleft()\n",
    "            for v in edges[u]:\n",
    "                indeg[v] -= 1\n",
    "                if indeg[v] == 0:\n",
    "                    q.append(v)\n",
    "\n",
    "        return visited == numCourses\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:\n",
    "        #拓扑排序\n",
    "        degree={i:0 for i in range(numCourses)}\n",
    "        graph={i:set() for i in range(numCourses)}\n",
    "        for edge in prerequisites:\n",
    "            i,j=edge[0],edge[1]\n",
    "            degree[i]+=1\n",
    "            graph[j].add(i)\n",
    "        q=[i for i in range(numCourses) if degree[i]==0]\n",
    "        res=[]\n",
    "        while q:\n",
    "            node=q.pop()\n",
    "            res.append(node)\n",
    "            for next_node in graph[node]:\n",
    "                degree[next_node]-=1\n",
    "                if degree[next_node]==0:\n",
    "                    q.append(next_node)\n",
    "        return len(res)==numCourses\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# topological sorting\n",
    "from collections import defaultdict, deque\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:\n",
    "        nxt_courses = defaultdict(set)\n",
    "        req_courses = defaultdict(set)\n",
    "        for nxt, req in prerequisites:\n",
    "            nxt_courses[req].add(nxt)\n",
    "            req_courses[nxt].add(req)\n",
    "        \n",
    "        q = deque()\n",
    "        for i in range(numCourses):\n",
    "            if i not in req_courses:\n",
    "                q.append(i)\n",
    "        taken = set()\n",
    "        \n",
    "        while q:\n",
    "            cur = q.pop()\n",
    "            taken.add(cur)\n",
    "            for nxt in nxt_courses[cur]:\n",
    "                req_courses[nxt].remove(cur)\n",
    "                if (not req_courses[nxt] or len(req_courses[nxt]) == 0) and nxt not in taken:\n",
    "                    q.appendleft(nxt)\n",
    "                    taken.add(nxt)\n",
    "        \n",
    "        return len(taken) == numCourses\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:\n",
    "        import collections\n",
    "        edges = collections.defaultdict(list)\n",
    "        indegree = [0] * numCourses\n",
    "        for prerequisite in prerequisites:\n",
    "            edges[prerequisite[0]].append(prerequisite[1])\n",
    "            indegree[prerequisite[0]] += 1\n",
    "        q = collections.deque()\n",
    "        for i in range(numCourses):\n",
    "            if indegree[i] == 0:\n",
    "                q.append(i)\n",
    "        while q:\n",
    "            l = q.popleft()\n",
    "            for node in edges.keys():\n",
    "                if l in edges[node]:\n",
    "                    # edges[node].remove(l)\n",
    "                    indegree[node] -= 1\n",
    "                    if indegree[node] == 0:\n",
    "                        q.append(node)\n",
    "        return sum(indegree) == 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:\n",
    "        if not prerequisites:\n",
    "            return True \n",
    "\n",
    "        graph, indegree = self.build_graph(prerequisites, numCourses)\n",
    "        queue = collections.deque([c for c in range(numCourses) if indegree[c] == 0])\n",
    "        \n",
    "        cnt = 0\n",
    "        while queue:\n",
    "            cur_c = queue.popleft()\n",
    "            cnt += 1\n",
    "            for neighbor in graph[cur_c]:\n",
    "                indegree[neighbor] -= 1\n",
    "                if indegree[neighbor] == 0:\n",
    "                    queue.append(neighbor)\n",
    "        \n",
    "        return cnt == numCourses\n",
    "\n",
    "        \n",
    "    \n",
    "    def build_graph(self, prerequisites, numCourses):\n",
    "        graph = [[] for _ in range(numCourses)]\n",
    "        indegree = [0] * numCourses\n",
    "\n",
    "        for in_, out_ in prerequisites:\n",
    "            graph[out_].append(in_)\n",
    "            indegree[in_] += 1\n",
    "\n",
    "        return graph, indegree        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:\n",
    "        from collections import deque\n",
    "        if len(prerequisites) == 0:\n",
    "            return True\n",
    "        res = numCourses\n",
    "        que = deque()\n",
    "        adj = [[] for _ in range(numCourses)]\n",
    "        indegree = [0]*numCourses\n",
    "        for second, first in prerequisites:\n",
    "            indegree[second] += 1\n",
    "            adj[first].append(second)\n",
    "        for i in range(len(indegree)):\n",
    "            if indegree[i]==0:\n",
    "                que.append(i)\n",
    "        while que:\n",
    "            # 取出队首元素，并将其邻接的入度减一\n",
    "            cur = que.popleft()\n",
    "            res -= 1\n",
    "            for i in range(len(adj[cur])):\n",
    "                indegree[adj[cur][i]] -= 1\n",
    "                if indegree[adj[cur][i]] == 0:\n",
    "                    que.append(adj[cur][i])\n",
    "            \n",
    "        return True if not res else False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:\n",
    "        edges = collections.defaultdict(list)\n",
    "        inedges = [0] * numCourses\n",
    "        for pre in prerequisites:\n",
    "            edges[pre[1]].append(pre[0])\n",
    "            inedges[pre[0]] += 1\n",
    "        q = collections.deque([u for u in range(numCourses) if inedges[u] == 0])\n",
    "        count = 0\n",
    "        while q:\n",
    "            u = q.popleft()\n",
    "            count += 1\n",
    "            for v in edges[u]:\n",
    "                inedges[v] -= 1\n",
    "                if inedges[v] == 0:\n",
    "                    q.append(v)\n",
    "        return count == numCourses"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:\n",
    "        indegrees = [0 for _ in range(numCourses)]\n",
    "        adjacency = [[] for _ in range(numCourses)]\n",
    "        queue = deque()\n",
    "        # Get the indegree and adjacency of every course.\n",
    "        for cur, pre in prerequisites:\n",
    "            indegrees[cur] += 1\n",
    "            adjacency[pre].append(cur)\n",
    "        # Get all the courses with the indegree of 0.\n",
    "        for i in range(len(indegrees)):\n",
    "            if not indegrees[i]: queue.append(i)\n",
    "        # BFS TopSort.\n",
    "        while queue:\n",
    "            pre = queue.popleft()\n",
    "            numCourses -= 1\n",
    "            for cur in adjacency[pre]:\n",
    "                indegrees[cur] -= 1\n",
    "                if not indegrees[cur]: queue.append(cur)\n",
    "        return not numCourses\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:\n",
    "        adj = [[] for _ in range(numCourses)]\n",
    "        in_degree = [0] * numCourses\n",
    "        for cur, pre in prerequisites:\n",
    "            in_degree[cur] += 1\n",
    "            adj[pre].append(cur)\n",
    "        queue = []\n",
    "        for i in range(numCourses):\n",
    "            if in_degree[i] == 0:\n",
    "                queue.append(i)\n",
    "        count = 0\n",
    "        while queue:\n",
    "            q = queue.pop(0)\n",
    "            count += 1\n",
    "            for i in adj[q]:\n",
    "                in_degree[i] -= 1\n",
    "                if in_degree[i] == 0:\n",
    "                    queue.append(i)\n",
    "        return count == numCourses\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # def dfs(i, adj, flags):\n",
    "        #     if flags[i] == -1:\n",
    "        #         return True\n",
    "        #     if flags[i] == 1:\n",
    "        #         return False\n",
    "        #     flags[i] = 1\n",
    "        #     for j in adj[i]:\n",
    "        #         if not dfs(j, adj, flags):\n",
    "        #             return False\n",
    "        #     flags[i] = -1\n",
    "        #     return True\n",
    "        # adj = [[] for _ in range(numCourses)]\n",
    "        # flags = [0] * numCourses\n",
    "        # for cur, pre in prerequisites:\n",
    "        #     adj[pre].append(cur)\n",
    "        # for i in range(numCourses):\n",
    "        #     if not dfs(i, adj, flags):\n",
    "        #         return False\n",
    "        # return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def build_graph(numCourses: int, prerequisites: List[List[int]]):\n",
    "    graph = {node: set() for node in range(numCourses)}\n",
    "    for edge in prerequisites:\n",
    "        from_, to_ = edge[1], edge[0]\n",
    "        graph[from_].add(to_)\n",
    "    return graph\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def canFinish(self,\n",
    "                  numCourses: int,\n",
    "                  prerequisites: List[List[int]]) -> bool:\n",
    "        graph = build_graph(numCourses, prerequisites)\n",
    "        indegree = [0] * numCourses\n",
    "        for edge in prerequisites:\n",
    "            indegree[edge[0]] += 1\n",
    "        q = deque()\n",
    "        # 找出入度为零的课程作为开始\n",
    "        for i in range(numCourses):\n",
    "            if indegree[i] == 0:\n",
    "                q.append(i)\n",
    "        count = 0\n",
    "        while q:\n",
    "            # pop(0) 即取出第一个元素，实现队列访问\n",
    "            cur = q.popleft()\n",
    "            count += 1\n",
    "            for next_ in graph[cur]:\n",
    "                indegree[next_] -= 1\n",
    "                if indegree[next_] == 0:\n",
    "                    q.append(next_)\n",
    "        return count == numCourses"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "class Solution:\n",
    "    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:\n",
    "        edges = collections.defaultdict(list)\n",
    "        indeg = [0] * numCourses\n",
    "        res = []\n",
    "\n",
    "        for nodelist in prerequisites:\n",
    "            edges[nodelist[1]].append(nodelist[0])\n",
    "            indeg[nodelist[0]] +=1\n",
    "        \n",
    "        q = collections.deque([n for n in range(numCourses) if indeg[n] == 0])\n",
    "\n",
    "        while q:\n",
    "            u = q.popleft()\n",
    "            res.append(u)\n",
    "            for neighbor in edges[u]:\n",
    "                indeg[neighbor] -=1\n",
    "                if indeg[neighbor] == 0:\n",
    "                    q.append(neighbor)\n",
    "        \n",
    "        if len(res) != numCourses:\n",
    "            return False\n",
    "        else:\n",
    "            return True\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:\n",
    "        n = len(prerequisites)\n",
    "        inorder, adjust = [0]*numCourses, collections.defaultdict(list)\n",
    "\n",
    "        for cur,pre in prerequisites:\n",
    "            adjust[pre].append(cur)\n",
    "            inorder[cur] += 1\n",
    "        \n",
    "        stack = []\n",
    "        for i in range(numCourses):\n",
    "            if inorder[i] == 0:\n",
    "                stack.append(i)\n",
    "                numCourses -= 1\n",
    "        \n",
    "        while stack:\n",
    "            pre = stack.pop()\n",
    "            for cur in adjust[pre]:\n",
    "                inorder[cur] -= 1\n",
    "\n",
    "                if inorder[cur] == 0:\n",
    "                    stack.append(cur)\n",
    "                    numCourses -= 1\n",
    "\n",
    "        return not numCourses"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:\n",
    "        graph = collections.defaultdict(list) # val is neighbors\n",
    "        indeg = [0]*numCourses\n",
    "        # Build Graph\n",
    "        for prereq in prerequisites:\n",
    "            graph[prereq[1]].append(prereq[0])\n",
    "            indeg[prereq[0]] += 1\n",
    "        \n",
    "        bfs = deque([i for i in range(numCourses) if indeg[i] == 0])\n",
    "        visited = len(bfs)\n",
    "        while bfs:\n",
    "            course = bfs[0]\n",
    "            bfs.popleft()\n",
    "            for neighbor in graph[course]:\n",
    "                indeg[neighbor] -= 1\n",
    "                if not indeg[neighbor]:\n",
    "                    bfs.append(neighbor)\n",
    "                    visited += 1\n",
    "\n",
    "        return visited == numCourses"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:\n",
    "\n",
    "        indeg = defaultdict(int)\n",
    "        rela = defaultdict(list)\n",
    "        for x, y in prerequisites:\n",
    "            indeg[x] += 1\n",
    "            rela[y].append(x)\n",
    "        print(indeg)\n",
    "        print(rela)\n",
    "        q = [x for x in range(numCourses) if x not in indeg]\n",
    "        tmp = []\n",
    "        while q:\n",
    "            v = q.pop(0)\n",
    "            numCourses -= 1\n",
    "            for i in rela.get(v, []):\n",
    "                indeg[i] -= 1\n",
    "                if indeg[i] == 0:\n",
    "                    tmp.append(i)\n",
    "            if not q:\n",
    "                q.extend(tmp)\n",
    "                tmp.clear()\n",
    "\n",
    "\n",
    "        return numCourses == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:\n",
    "        in_map = {}\n",
    "        out_map = {}\n",
    "        for i in range(numCourses):\n",
    "            in_map[i] = set()\n",
    "            out_map[i] = set()\n",
    "        for i,j in prerequisites:\n",
    "            in_map[j].add(i)\n",
    "            out_map[i].add(j)\n",
    "        for i in range(numCourses):\n",
    "            flag = False\n",
    "            for v in in_map:\n",
    "                if len(in_map[v]) == 0:\n",
    "                    in_map.pop(v)\n",
    "                    for u in out_map[v]:\n",
    "                        in_map[u].discard(v)\n",
    "                    flag = True\n",
    "                    break  \n",
    "            if flag is False:\n",
    "                return False\n",
    "                \n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:\n",
    "\n",
    "        forward, backward = defaultdict(set), defaultdict(set)\n",
    "        for b, a in prerequisites:\n",
    "            forward[a].add(b)\n",
    "            backward[b].add(a)\n",
    "        \n",
    "        cur_layer = set(node for node in range(numCourses) if node not in backward) # cur_layer中都无前置节点\n",
    "        while len(cur_layer) > 0:\n",
    "            for node in cur_layer.copy():\n",
    "                cur_layer.discard(node)\n",
    "                for next_node in forward[node]:\n",
    "                    backward[next_node].discard(node)\n",
    "                    if len(backward[next_node]) == 0:\n",
    "                        del backward[next_node]\n",
    "                        cur_layer.add(next_node)\n",
    "                numCourses -= 1\n",
    "        \n",
    "        if numCourses > 0:\n",
    "            return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:\n",
    "        pre_dict = defaultdict(set)\n",
    "        suc_dict = defaultdict(set)\n",
    "        for suc, pre in prerequisites:\n",
    "            pre_dict[suc].add(pre)\n",
    "            suc_dict[pre].add(suc)\n",
    "            # a cycle\n",
    "            # if suc in pre_dict[pre]:\n",
    "                # return False\n",
    "        all_course_set = set(range(numCourses))\n",
    "        can_finish = True\n",
    "        while can_finish:\n",
    "            free_course_set = all_course_set - set(pre_dict.keys())\n",
    "            if len(free_course_set) == 0:\n",
    "                return False\n",
    "            for course in free_course_set:\n",
    "                all_course_set.discard(course)\n",
    "                for key in suc_dict[course]:\n",
    "                    pre_dict[key].discard(course)\n",
    "                    if len(pre_dict[key]) == 0:\n",
    "                        pre_dict.pop(key)\n",
    "                suc_dict.pop(course)\n",
    "            if len(all_course_set) == 0:\n",
    "                return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self,val):\n",
    "        self.val = val\n",
    "        self.aft = []\n",
    "        self.pre = []\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.course = dict()\n",
    "    def canFinish(self, numCourses: int, prerequisites) -> bool:\n",
    "        nums = 0\n",
    "        for i in prerequisites:\n",
    "            a,b = i[0],i[1]\n",
    "            if a not in self.course:\n",
    "                self.course[a] = Node(a)\n",
    "            if b not in self.course:\n",
    "                self.course[b] = Node(b)\n",
    "            self.course[a].pre.append(self.course[b])\n",
    "            self.course[b].aft.append(self.course[a])\n",
    "        for i in self.course:\n",
    "            if not self.course[i].pre:\n",
    "                learned = [self.course[i]]\n",
    "                while learned:\n",
    "                    temp = []\n",
    "                    for j in learned:\n",
    "                        if j.val != \"Q\":\n",
    "                            nums += 1\n",
    "                            j.val = \"Q\"\n",
    "                            for p in j.aft:\n",
    "                                flag = True\n",
    "                                for k in p.pre:\n",
    "                                    \n",
    "                                    if k.val != \"Q\":\n",
    "                                        flag = False\n",
    "                                        break\n",
    "                                if flag:\n",
    "                                    temp.append(p)\n",
    "                    learned = temp\n",
    "        return nums == len(self.course)\n",
    "\n",
    "S = Solution()\n",
    "print(S.canFinish(2,prerequisites = [[1,0],[0,1]]))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:\r\n",
    "        \r\n",
    "\r\n",
    "        # edges = collections.defaultdict(list)\r\n",
    "        # # 存储每个节点的入度\r\n",
    "        # indeg = [0] * numCourses\r\n",
    "        # # 存储答案\r\n",
    "        # result = list()\r\n",
    "\r\n",
    "        # for info in prerequisites:\r\n",
    "        #     edges[info[1]].append(info[0])\r\n",
    "        #     indeg[info[0]] += 1\r\n",
    "        \r\n",
    "        # # 将所有入度为 0 的节点放入队列中\r\n",
    "        # q = collections.deque([u for u in range(numCourses) if indeg[u] == 0])\r\n",
    "\r\n",
    "        # while q:\r\n",
    "        #     # 从队首取出一个节点\r\n",
    "        #     u = q.popleft()\r\n",
    "        #     # 放入答案中\r\n",
    "        #     result.append(u)\r\n",
    "        #     for v in edges[u]:\r\n",
    "        #         indeg[v] -= 1\r\n",
    "        #         # 如果相邻节点 v 的入度为 0，就可以选 v 对应的课程了\r\n",
    "        #         if indeg[v] == 0:\r\n",
    "        #             q.append(v)\r\n",
    "\r\n",
    "        # if len(result) != numCourses:\r\n",
    "        #     result = list()\r\n",
    "        # return result\r\n",
    "        def dfs(i,adjacence,flags):\r\n",
    "            if (flags[i] == -1 ):return True\r\n",
    "            if(flags[i] == 1):return False\r\n",
    "            flags[i] = 1\r\n",
    "            for j in adjacence[i]:\r\n",
    "                if not dfs(j,adjacence,flags):return False\r\n",
    "            flags[i] = -1\r\n",
    "            return True\r\n",
    "        adjacency = [[] for _ in range(numCourses)]\r\n",
    "        flags = [0 for _ in range(numCourses)]\r\n",
    "        for cur , pre in prerequisites:\r\n",
    "            adjacency[pre].append(cur)\r\n",
    "        for i in range(numCourses):\r\n",
    "            if not dfs(i,adjacency,flags) :return False\r\n",
    "        return True\r\n",
    "                \r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:\n",
    "        def dfs(i, dep, flags):\n",
    "            if flags[i] == 1:\n",
    "                return False\n",
    "            if flags[i] == -1:\n",
    "                return True\n",
    "            flags[i] = 1\n",
    "            for j in dep[i]:\n",
    "                if not dfs(j, dep, flags):\n",
    "                    return False\n",
    "            flags[i] = -1\n",
    "            return True\n",
    "\n",
    "        dep = [[] for _ in range(numCourses)]\n",
    "        flags = [0] * numCourses\n",
    "\n",
    "        for cur, pre in prerequisites:\n",
    "            dep[cur].append(pre)\n",
    "        \n",
    "        for i in range(numCourses):\n",
    "            if not dfs(i, dep, flags):\n",
    "                return False\n",
    "\n",
    "        return True\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:\n",
    "        graph = collections.defaultdict(list) # val is neighbors\n",
    "        visit_status = [0] * numCourses # 0: not searched; 1: searching; 2: finished\n",
    "        # Build Graph\n",
    "        for prereq in prerequisites:\n",
    "            graph[prereq[1]].append(prereq[0])\n",
    "        \n",
    "        def dfs(course):\n",
    "            if visit_status[course] == 2: return True\n",
    "            elif visit_status[course] == 1: return False\n",
    "\n",
    "            visit_status[course] = 1\n",
    "            for neighbor in graph[course]:\n",
    "                if not dfs(neighbor): return False\n",
    "            visit_status[course] = 2\n",
    "            return True\n",
    "\n",
    "        for course in range(numCourses):\n",
    "            if not visit_status[course]: \n",
    "                if not dfs(course): return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:\n",
    "        edges = collections.defaultdict(list)\n",
    "        visited = [0] * numCourses\n",
    "        result = list()\n",
    "        valid = True\n",
    "\n",
    "        for info in prerequisites:\n",
    "            edges[info[0]].append(info[1])\n",
    "        \n",
    "        def dfs(u: int):\n",
    "            nonlocal valid\n",
    "            visited[u] = 1\n",
    "            for v in edges[u]:\n",
    "                if visited[v] == 0:\n",
    "                    dfs(v)\n",
    "                    if not valid:\n",
    "                        return\n",
    "                elif visited[v] == 1:\n",
    "                    valid = False\n",
    "                    return\n",
    "            visited[u] = 2\n",
    "            result.append(u)\n",
    "        \n",
    "        for i in range(numCourses):\n",
    "            if valid and not visited[i]:\n",
    "                dfs(i)\n",
    "        \n",
    "        return valid"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
